package algorithm.sort.merge;


import java.util.Arrays;

public class MergeSort2 {
    public static void sort(int[] data) {
        int[] result = sortPart(data);
        for (int i = 0; i < result.length; i++) {
            data[i] = result[i];
        }
    }

    public static int[] sortPart(int[] data) {
        if(data.length<2){
            return Arrays.copyOfRange(data, 0, data.length);
        }
        int mid = data.length / 2;
        int[] left = Arrays.copyOfRange(data, 0, mid);
        int[] right = Arrays.copyOfRange(data, mid, data.length);
        return mergeParts(sortPart(left), sortPart(right));
    }

    public static int[] mergeParts(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int leftIndex = 0;
        int rightIndex = 0;
        int resultIndex = 0;
        while (true) {
            if (leftIndex < left.length && rightIndex < right.length) {
                if (left[leftIndex] < right[rightIndex]) {
                    result[resultIndex++] = left[leftIndex++];
                } else {
                    result[resultIndex++] = right[rightIndex++];
                }
            } else if (leftIndex < left.length && rightIndex >= right.length) {
                result[resultIndex++] = left[leftIndex++];
            } else if (leftIndex >= left.length && rightIndex < right.length) {
                result[resultIndex++] = right[rightIndex++];
            } else {
                break;
            }
        }
        return result;
    }
}
